package com.smh;

import org.junit.jupiter.api.Test;
import com.smh._013_队列_链表.MyQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author shiminghui
 * @date 2025/2/10 18:09
 * @description: TODO
 */
public class _015_队列_二叉树层序遍历 {

    @Test
    public void test1() {
        TreeNode<Integer> treeNode = new TreeNode<>(
                new TreeNode<>(
                        new TreeNode<>(4),
                        2,
                        new TreeNode<>(5)
                ),
                1,
                new TreeNode<>(
                        new TreeNode<>(6),
                        3,
                        new TreeNode<>(7)
                )
        );
        levelOrder(treeNode);
        Queue<TreeNode<Integer>> integers = new LinkedList<>();
    }

    // 层序遍历二叉树
    public void levelOrder(TreeNode<Integer> root) {
        if (root == null) {
            return;
        }
        MyQueue<TreeNode<Integer>> queue = new MyQueue<>();
        queue.offer(root);
        int c1 = 1; // 当前层节点数
        while (!queue.isEmpty()) {
            int c2 = 0; // 下一层节点数
            for (int i = 0; i < c1; i++) {
                TreeNode<Integer> node = queue.poll();
                System.out.print(node.value + "  ");
                if (node.left != null) {
                    queue.offer(node.left);
                    c2++;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    c2++;
                }
            }
            c1 = c2;
            System.out.println();
        }
    }

    public List<List<Integer>> levelOrder2(TreeNode<Integer> root) {
        if (root == null) {
            return null;
        }
        ArrayList<List<Integer>> res = new ArrayList<>();
        MyQueue<TreeNode<Integer>> queue = new MyQueue<>();
        queue.offer(root);
        int c1 = 1;
        while (!queue.isEmpty()) {
            int c2 = 0;
            ArrayList<Integer> a = new ArrayList<>();
            for (int i = 0; i < c1; i++) {
                TreeNode<Integer> poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                    c2++;
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                    c2++;
                }
                a.add(poll.value);
                c1 = c2;
            }
            res.add(a);
        }
        return res;
    }


    private static class TreeNode<T> {
        private T value;
        private TreeNode<T> left;
        private TreeNode<T> right;

        public TreeNode(T value) {
            this.value = value;
        }

        public TreeNode(TreeNode<T> left, T value, TreeNode<T> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public TreeNode() {
        }
    }

}
